#include <iostream>
#include <vector>

using namespace std;

// 283. 移动零
// https://leetcode.cn/problems/move-zeroes/description/
// 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
// 时间复杂度: O(n)
// 空间复杂度: O(n)
// 方法：保序操作
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        // 保序操作，使用过滤器：非0就要，0就不要
        int n = 0;  // 原地的新表的下标
        //保序操作：使用过滤器思想。不一样的题目有不一样的过滤器，模板是一样的。
        for(int i = 0; i < nums.size(); i++) {
            if(nums[i] != 0) {    // 定义过滤器
                nums[n] = nums[i];  // 原地新表
                n++;
            }
        }
        // 后面补0
        while(n < nums.size()) {
            nums[n] = 0;
            n++;
        }
    }
};

int main() {

    int arr[] = {0, 1, 0, 3, 12};
    vector<int> vec(arr, arr + sizeof(arr)/sizeof(int));

    Solution().moveZeroes(vec);

    for(int i = 0 ; i < vec.size() ; i ++)
        cout << vec[i] << " ";
    cout << endl;

    return 0;
}